//
// Created by lanlu on 2025/8/14.
//

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    // source = "abcd", target = "acbe",
    // original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
    long long minimumCost(string source, string target,
            vector<char>& original, vector<char>& changed, vector<int>& cost) {
        long long INF = LONG_LONG_MAX/2;
        // 使用26*26的二维数组 记录源字符和目标字符的转换成本 即为图的邻接矩阵
        // 要注意 权重使用long long类型 用int会越界
        vector<vector<long long>> graph(26, vector<long long>(26, INF));
        // 将字符和自身的转换成本设为0
        for (int i = 0; i < 26; i++)
        {
            // 即为对角线
            graph[i][i] = 0;
        }

        // 将original和changed数组中的字符转换成本赋给graph
        for (int i = 0; i < original.size(); i++)
        {
            // 通过original获取行
            int x = original[i] - 'a';
            // 通过changed获取列
            int y = changed[i] - 'a';
            // 相同字母的映射可能有多个 此时取最小权重
            if (cost[i] < graph[x][y])
            {
                graph[x][y] = cost[i];
            }
        }

        // floyd算法 对应中间字符、起始字符、目标字符
        for (int k = 0; k < 26; k++)
        {
            for (int i = 0; i < 26; i++)
            {
                for (int j = 0; j < 26; j++)
                {
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }

        // 计算最小成本
        // source = "abcd", target = "acbe",
        long long res = 0;
        for (int i = 0; i < source.size(); i++)
        {
            int x = source[i] - 'a';
            int y = target[i] - 'a';
            if (graph[x][y] == INF)
            {
                // 不可达 直接返回
                return -1;
            }
            res += graph[x][y];
        }
        return res;

    }
};